﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
//这是一个有向的图，需要存在一个从0到n的路径
public class Solution210
{

    int[] visted;
    IList<IList<int>>  edges;
    int[] stack;
    int stackIndex;
    bool haveRing = false;
    public int[] FindOrder(int numCourses, int[][] prerequisites)
    {
        edges=new List<IList<int>>();
        stack = new int[numCourses];
        stackIndex = numCourses-1;
        for (int i = 0; i < numCourses; i++)
        {
            edges.Add(new List<int>());
        }
        //应该使用邻接表存

       
        for(int i = 0;i < prerequisites.Length; i++)
        {
            //[study,pre]
            //pre,先访问需要学习的，然后向后学习,study是所有的下一个节点
            edges[prerequisites[i][1]].Add(prerequisites[i][0]);
        }
        //判断这个图有没有一个可以用的排序
        visted = new int[numCourses];//三种状态，未搜索0，正在搜索1，搜索完毕2
        for (int i = 0; i < numCourses; i++)//遍历所有的节点(的所有邻接边edges)
        {
            if (visted[i] == 0)
            {
                DFS(i);
            }

           

        }
        if (haveRing)
        {
            return new int[0];//
        }

        return stack;
    }

    private void DFS(int curNode)//以这个为起点
    {
        visted[curNode] = 1;//搜索中
        


        for(int i = 0; i < edges[curNode].Count; i++)
        { //遍历当前节点(的所有邻接边edges)

            int nextNode = edges[curNode][i];
            if (visted[nextNode] == 0)//没搜索过的深入
            {
                DFS(nextNode);
                if(haveRing)//这个语句的作用待定,没啥用，不要也可以通过
                {
                    return;
                }
            }else if (visted[nextNode] == 1)//搜索中，有环
            {
                haveRing=true;
                return;
            }

           
        }
        //遍历完所i有的下一节点，入栈
        visted[curNode] = 2;//搜索完成
        //入栈，数组代替栈，数组0是栈顶，这样从前0往后，从顶到底就是顺序
        stack[stackIndex--] = curNode;


    }


}
public class Solution210_2
{

    int[] indeg;//入度
    IList<IList<int>> edges;
    int[] res;
    int resIndex;
  
    public int[] FindOrder(int numCourses, int[][] prerequisites)//BFS
    {
        edges = new List<IList<int>>();
        res = new int[numCourses];
        resIndex = 0;
        for (int i = 0; i < numCourses; i++)
        {
            edges.Add(new List<int>());
        }
        //应该使用邻接表存
    
        indeg = new int[numCourses];//节点的入度

        for (int i = 0; i < prerequisites.Length; i++)
        {
            //[study,pre]
            //pre,先访问需要学习的，然后向后学习,study是所有的下一个节点
            edges[prerequisites[i][1]].Add(prerequisites[i][0]);
            indeg[prerequisites[i][0]]++;

        }
        Queue<int> queue = new Queue<int>();
        
        for (int i = 0; i < numCourses; i++)//入度为0的作为起点，入队
        {

            if (indeg[i] == 0)
            {
                queue.Enqueue(i);
            }

        }
       
        while (queue.Count > 0)
        {
           int curNode= queue.Dequeue();
            res[resIndex++] = curNode;//加入结果


            for (int i = 0; i < edges[curNode].Count; i++)
            { //遍历当前节点(的所有邻接边edges)

                int nextNode= edges[curNode][i];

                indeg[nextNode]--;//下一个节点的入度减少，也就是先修课程完成了
                if (indeg[nextNode] == 0)//先修课程完成了入队 
                { queue.Enqueue(nextNode); }
            }


            }

        if (resIndex != numCourses)//说明有课程没学到
        {
            return new int[0];
        }

        return res;
        }
    

  


}
class Program210
{
    static void Main210(string[] args)
    {
        Solution210 solution2 = new Solution210();
        Solution210_2 solution = new ();
        int numCourses = 4;
        int[][] prerequisites = [[1, 0], [2, 0], [3, 1], [3, 2]];
        int[] res = solution.FindOrder(numCourses, prerequisites);
       
        for(int i = 0;i < res.Length;i++)
        {

            Console.WriteLine(res[i]);
        }
        
    }
}
